class LRUCache {
    /*
        LinkedHashMap:哈希表+双向链表
        空间复杂度：O(N)
        时间复杂度：O(1)
    */  
    Map<Integer,Integer> map = new LinkedHashMap<>();
    int maxLen;
    public LRUCache(int capacity) {
        this.maxLen = capacity;
    }

    public int get(int key) {
        int res;
        // 1.判断key是否存在
        if( map.containsKey(key) ){
            res = map.get(key);
            // 2.若存在，则把这个key从双向链表中删除，然后移动到末尾（最近使用的节点）
            makeRecently(key);
        }else{
            res = -1;
        }
        return res;
    }
    /*
        删除最久未使用的数据值：即没有put或者get
    */
    public void put(int key, int value) {
        // 1.判断元素是否存在
        if(map.containsKey(key)){
            // 元素存在，插入元素后需要把节点移到末尾
            map.put(key,value);
            makeRecently(key);
        }
        // 2.若元素不存在，有两种情况：空间满了和没满
        else {
            // 2.1如果空间满了，就要删除最早未使用的key
            if( map.size()>=maxLen ){
                map.remove(map.keySet().iterator().next());
            }
            map.put(key,value);
        }
    }
    public void makeRecently(int key){
        int val = map.get(key);
        map.remove(key);
        map.put(key,val);
    }
}